Программа

Полный документ с описанием авторской образовательной программы «Основы программирования, классические алгоритмы и структуры данных, олимпиадное программирование»  Краснодарской школы программирования можно скачать здесь: Образовательная программа.

Ниже представлено содержание программы.

Раздел 1 программы предназначен для широкого круга учащихся и ориентирован на учащихся без опыта изучения программирования или с минимальным опытом. Основной возраст освоения материала: учащиеся 5 — 7 классов общеобразовательной школы. Индивидуально могут быть отступления от этого возрастного ориентира как в сторону младшего, так и в сторону старшего возраста. Срок освоения данного раздела программы: от 1 до 3 лет в зависимости от возраста и индивидуальных особенностей учащихся. Набор учащихся осуществляется на общих основаниях по результатам отборочной сессии, которая обычно проходит в течение одной недели в июне на следующий учебных год (приглашаются школьники, перешедшие в 5 — 7 класс).

Раздел 1. Основы программирования

1. Простейшие программы на C++, основные операции и ветвление
2. Циклы
3. Обработка числовой последовательности
4. Одномерные числовые массивы
5. Простейшие алгоритмы арифметики и теории чисел. Понятие сложности алгоритма, О-нотация
6. Двумерные числовые массивы
7. Строки
8. Структуры, функции и рекурсия
9. Одномерные числовые массивы: метод двух указателей
10. Сортировка
11. Основы комбинаторики. Перебор вариантов
12. Формула включений-исключений
13. Геометрия на прямой
14. Введение в Python
15. Длинная арифметика

Раздел 2 программы предназначен для школьников, освоивших на достаточном уровне материал Раздела 1 программы или владеющих программированием и решением задач по программированию на соответствующем уровне (в целом соответствующем уровню освоения материала Раздела 1). В рамках изучения раздела проводятся занятия по олимпиадному программированию: решение индивидуальных и командных олимпиад по соответствующим темам и соответствующего уровня сложности. Основной возраст освоения материала: учащиеся 7 — 10 классов общеобразовательной школы. Срок освоения материала: 1 — 3 лет в зависимости от возраста и индивидуальных особенностей учащихся.

Раздел 2. Классические алгоритмы и структуры данных. Олимпиадное программирование

1. Линейные структуры данных
   1. Стек
   2. Очередь
   3. Дек
   4. Применение линейных структур для решения некоторых задач обработки массивов
2. Введение в задачи на графах: методы обхода графа
   1. Представление графа
   2. Обход в глубину
   3. Обход в ширину
   4. Обход в ширину 0-1
3. Бинарный поиск
4. Конечные автоматы в обработке текстовых данных
5. Индуктивные функции и динамическое программирование. Задача о рюкзаке.
6. Игры и стратегии
7. Более сложные алгоритмы арифметики и теории чисел
8. Подсчёт количеств
9. Двусвязные списки
10. Корневая декомпозиция
11. Представление множеств: хэширование
12. Представление множеств: деревья
    1. Бинарное несбалансированное дерево
    2. АВЛ-дерево
    3. Красно-чёрные деревья
    4. B-деревья
13. Префиксные суммы, дерево отрезков
    1. Префиксные суммы на одномерном числовом массиве
    2. Двумерные префиксные суммы
    3. Дерево отрезков:
       1. Построение
       2. Использование
       3. Обновление элементов
       4. Массовое обновление элементов
       5. Примеры применений
14. Куча
15. Система не пересекающихся множеств

Раздел 3. Более сложные алгоритмы и структуры данных

Раздел 3 является дополнительным разделом программы повышенной сложности и ориентирован на учащихся, на должном уровне владеющих материалом первых двух разделов. Также в качестве требований к учащимся для начала освоения данного раздела предъявляется требование наличия достаточного богатого олимпиадного опыта и наличия олимпиадных достижений (результаты на региональном этапе ВсОШ по информатике, результаты в олимпиадах РСОШ, результаты в олимпиаде ВКОШП). Основной возраст освоения материала: учащиеся 9 — 11 классов общеобразовательной школы. Срок освоения материала: 1 — 3 лет в зависимости от возраста и индивидуальных особенностей учащихся.

1. Кратчайшие пути в графах
   1. Алгоритм Флойда
   2. Алгоритм Форда-Беллмана
   3. Алгоритм Дейкстры
2. Декартово дерево
3. Разреженные таблицы
4. Поиск в тексте и в словаре
   1. Бор
   2. Сжатый бор
   3. Суффиксный бор
   4. Хэширование на строках
   5. Префикс-функция и Z-функция
   6. Алгоритм Ахо-Корасик
5. Более сложные задачи на графах
   1. Поиск мостов
   2. Поиск точек сочленения
   3. Поиск наименьшего общего предка в дереве
   4. Диаметр дерева
   5. Центровая декомпозиция дерева
   6. Обход в ширину 1-k
   7. Трехдольность дерева, Задача комивояжера и понятие NP-полноты
6. Вычислительная геометрия
7. Выпуклые оболочки
8. Многоугольники на плоскости
9. Оптимизационные задачи
10. Задача 2-SAT
11. Паросочетания
12. Потоки
13. Методы оптимизации алгоритмов динамического программирования
    1. Метод двоичного подъема
    2. Метод выпуклой огибающей
14. Персистентные структуры
15. Более сложные теоретико-числовые алгоритмы и основы криптографии